package leetcode.pre100;

import utils.ListNode;
import utils.ListUtil;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 * 示例 2:
 *
 * 输入: 0->1->2->NULL, k = 4
 * 输出: 2->0->1->NULL
 * 解释:
 * 向右旋转 1 步: 2->0->1->NULL
 * 向右旋转 2 步: 1->2->0->NULL
 * 向右旋转 3 步: 0->1->2->NULL
 * 向右旋转 4 步: 2->0->1->NULL
 * @date 2020/6/6 15:03
 */
public class Code61_RotateList_旋转链表 {
    public static void main(String[] args) {
        Code61_RotateList_旋转链表 p = new Code61_RotateList_旋转链表();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
//        node.next.next = new ListNode(3);
//        node.next.next.next = new ListNode(4);
//        node.next.next.next.next = new ListNode(5);
        ListNode listNode = p.rotateRight1(node, 2);
        ListUtil.printLinkedList(listNode);
    }
    /**
     * 方式1：
     * 把list的值存到数组中，在数组中找到右移后的起点，
     * 遍历链表赋值
     * 时空都是O(n)
     */
    public ListNode rotateRight1(ListNode head,int k) {
        if(k <= 0 || head == null || head.next == null) return head;
        ListNode p = head;
        List<Integer> list = new LinkedList<>();
        while (p != null){
            list.add(p.val);
             p = p.next;
        }
        Integer[] nums = list.toArray(new Integer[0]);
        int len = list.size();
        k %= len;
        if(k == 0)return head;
        int start = len - k;
        p = head;
        while (p != null){
            p.val = nums[start++];
            start %= len;
            p = p.next;
        }
        return head;
    }

    /**
     * 方式2：
     * 1->2->3->4->5    k = 2或者k = 7
     * 4->5->1->2->3
     *
     * 1)向右移动k个节点，等价于从倒数第k个节点开始为新的头
     * 2)倒数第k个节点，就是正数第len-k+1个节点开始
     * 3)找到第len-k个节点p，其为移动后的尾巴，找到第len-k+1，其为头
     * 4）把旧的尾巴连接到旧的头
     */
    public ListNode rotateRight2(ListNode head, int k) {
        if(head == null) return head;
        if(k <= 0) return head;
        int len = 0;
        ListNode p = head;
        while(p != null){
            p = p.next;
            len++;
        }
        k %= len;
        //不用移动
        if(k == 0)return head;
        //向右移动第k个，等价于 从倒数第k个节点开始算新链表的头部
        //倒数第k个节点就是正数第 len - k + 1个节点
        //先找到第len - k个节点，把其next设置为null
        //然后找到第 len - k + 1个，作为节点的头
        k = len - k;
        p = head;
        k --;
        //找到第k个节点
        while(k != 0){
            p = p.next;
            k--;
        }
        ListNode newHead = p.next;
        p.next = null;
        //新的头
        p = newHead;
        //新头找到尾巴，和旧的头连接
        while(newHead.next != null) newHead = newHead.next;
        newHead.next = head;
        return p;
    }
}
